package leet;

import org.junit.Test;

import java.util.*;

/**
 * @author fance
 * @date 2018/6/7 9:08
 */
public class DailyCode {
    /**
     * 804. Unique Morse Code Words
     * @param words
     * @return
     */
    public int uniqueMorseRepresentations(String[] words) {
        if (words == null || words.length < 1) {
            return 0;
        }
        String[] arr = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        Set<String> set = new HashSet<>();
        for (String s : words) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                stringBuilder.append(arr[s.charAt(i) - 'a']);
            }
            set.add(stringBuilder.toString());
        }
        return set.size();
    }

    /**
     * 485. 最大连续1的个数
     * @param nums
     * @return
     */
    public int findMaxConsecutiveOnes(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int max = 0;
        int cur = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 1) {
                cur = 0;
            } else {
                cur++;
                max = Math.max(max,cur);
            }
        }
        return max;
    }

    /**
     * 287. 寻找重复数 堆排序，然后遍历
     *
     不能更改原数组（假设数组是只读的）。 sort pass
     只能使用额外的 O(1) 的空间。 ???
     时间复杂度小于 O(n2) 。  bf pass
     数组中只有一个重复的数字，但它可能不止重复出现一次。
     * @param nums
     * @return
     */
    public int findDuplicate(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == nums[i]) {
                    res = nums[i];
                }
            }
        }
        return res;
    }

    /**
     * 131. 分割回文串
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null || s.length() < 1) {
            return res;
        }
        backTrackForPartition(res,new ArrayList<>(),s,0);
        return res;
    }
    private void backTrackForPartition(List<List<String>> res,
                                       List<String> cur,
                                       String s,
                                       int start) {
    if (start == s.length()) {
        res.add(new ArrayList<>(cur));
    } else {
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s,start,i)) {
                cur.add(s.substring(start,i + 1));
                backTrackForPartition(res,cur,s,i + 1);
                cur.remove(cur.size() - 1);
            }
        }
        }
    }
    private boolean isPalindrome(String s, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo++) != s.charAt(hi--)) {
                return false;
            }
        }
        return true;
    }


    /**
     * 540. 有序数组中的单一元素  
     * @param nums
     * @return
     */
    public int singleNonDuplicateI(int[] nums) {
        int res = 0;
        for (int i : nums) {
            res ^= i;
        }
        return res;
    }
    public int singleNonDuplicateII(int[] nums) {
        int len = nums.length;
        if (nums[0] != nums[1] && nums[1] == nums[2]) {
            return nums[0];
        }
        if (nums[len - 1] != nums[len - 2] && nums[len - 2] == nums[len - 3]) {
            return nums[len - 1];
        }
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return -1;
    }

    public int singleNonDuplicateIII(int[] nums) {
        int i = 0;
        boolean found = false;
        int index = 0;
        while (i < nums.length - 1) {
            if (nums[i] == nums[i + 1]) {
                i = i + 2;
                continue;
            } else {
                found = true;
                index = i;
            }
            i++;
        }
        if (found == false) {
            return nums[nums.length - 1];
        }
        return nums[index];
    }

    /**
     *476. 数字的补数
     * @param num
     * @return
     */
    public int findComplement(int num) {
       String s =  Integer.toBinaryString(num);
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '1') {
                stringBuilder.append("0");
            } else {
                stringBuilder.append("1");
            }
        }
        return Integer.parseInt(stringBuilder.toString(),2);
    }

    /**
     * 120. 三角形最小路径和
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp = new int[triangle.size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = Math.min(dp[j],dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }

    /**
     * 414. 第三大的数
     * @param nums
     * @return
     */
    public int thirdMax(int[] nums) {
        Integer max1 = null;
        Integer max2 = null;
        Integer max3 = null;
        for (Integer n : nums) {
            if (n.equals(max1) || n.equals(max2) || n.equals(max3)) {
                continue;
            }

            if (max1 == null || n > max1) {
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (max2 == null || n > max2) {
                max3 = max2;
                max2 = n;
            } else if (max3 == null || n > max3){
                max3 = n;
            }
        }
        return max3 == null ? max1 : max3;
     }

    /**
     * 215. 数组中的第K个最大元素
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int n : nums) {
            priorityQueue.offer(n);
            while (priorityQueue.size() > k) {
                priorityQueue.poll();
            }

        }
        return priorityQueue.peek();
    }
     @Test
    public void test() {
       /* String[] words = {"gin", "zen", "gig", "msg"};
        System.out.println(uniqueMorseRepresentations(words));*/
       /*int[] a = {1,1,0,1,1,1};
        System.out.println(findMaxConsecutiveOnes(a));*/
       /* System.out.println(findComplement(5));
        System.out.println(findComplement(1));
   */
       /*  System.out.println(thirdMax(a));
         System.out.println(thirdMax(b));*/
        int[] a = {3,2,1,5,6,4};
        int[] b = {3,2,3,1,2,4,5,5,6};
         System.out.println(findKthLargest(a,2));
         System.out.println(findKthLargest(b,4));

    }
}
